package com.lwx.algorithm.chapter6;

import com.lwx.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Offer144Two {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<Command> stack = new Stack<>();
        stack.push(new Command("go",root));
        while (!stack.isEmpty()) {
            Command current = stack.pop();
            if(current.getS().equals("print")){
                ret.add(Integer.valueOf(current.getS()));
            }else if(current.getS().equals("go")){
                TreeNode currentNode = current.getNode();
                if(null != currentNode.getRight()){
                    stack.push(new Command("go",currentNode.getRight()));
                }
                if(null != currentNode.getLeft()){
                    stack.push(new Command("go",currentNode.getLeft()));
                }
                stack.push(new Command("push",currentNode));
            }
        }
        return ret;
    }
}
